package com.ting.test.algorithms.链表;

import java.util.Stack;

/**
 * 给定一个单链表的头节点head，请判断该链表是否为回文结构。
 * <p>
 * 1）哈希表方法特别简单（笔试用）
 * <p>
 * 2）改原链表的方法就需要注意边界了（面试用）
 * 思路
 * 利用栈的特性，先进后出，先把所有链表元素入栈，然后从头遍历链表，然后和栈中弹出的元素一一进行比对
 * <p>
 * 此时，遍历的第一个元素是链表的头部元素，而从栈中弹出的第一个元素是链表的尾部元素，如果二者一样，则进行下一轮
 * <p>
 * 如果完全一样，则表明，该链表元素是回文。
 */
public class 回文链表解法1 {
    public static void main(String[] args) {
        SingleNode head = new SingleNode();
        Boolean result = ishuiwen(head);
        System.out.println(result);
    }

    private static Boolean ishuiwen(SingleNode head) {
        if (head == null) {
            return false;
        }
        Stack<SingleNode> stack = new Stack<>();

        SingleNode node = head;
        stack.push(node);
        while (node.next != null) {
            stack.push(head.next);
            node = node.next;
        }
        SingleNode nodeV2 = head;
        do {
            if (nodeV2.getValue() != stack.pop().getValue()) {
                return false;
            }
            nodeV2 = nodeV2.next;
        } while (nodeV2.next != null);
        return true;
    }
}
